/*
 *https://leetcode.cn/problems/strange-printer/
 *lc664. 奇怪的打印机
 *medium 吴朝泽 2024.12.6
 *动态规划
*/

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int strangePrinter(string s) 
    {
        int n = s.size();
        int dp[n][n];
        memset(dp, 0x3f, sizeof(dp));
        for (int i = n - 1; ~i; --i) 
        {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; ++j) 
            {
                if (s[i] == s[j]) 
                    dp[i][j] = dp[i][j - 1];
                else 
                {
                    for (int k = i; k < j; ++k) 
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
        return dp[0][n - 1];
    }
};